/FONT#0=BDR25/FONT#1=BDJ25/FONT#2=SUB/FONT#3=NGB25/FONT#4=XMAS25
␈↓␈↓↓␈↓α␈↓β␈↓∧␈↓␈↓ ελRECURSION

␈↓ ↓H

␈↓ ↓H
␈↓ α_The␈α
term␈α
recursion␈α
refers␈α
to␈α
several␈α
related␈α
concepts␈α
in␈α
computer␈α
science␈α
and␈α
mathematics.

␈↓ ↓H

␈↓ ↓H
Recursion relation
␈↓ ↓H

␈↓ ↓H
␈↓ α_One␈α∞or␈α∞more␈α∞functions␈α∞of␈α∞an␈α∞integer␈α∞variable␈α∞is␈α∞defined␈α
by␈α
giving␈α
initial␈α
values␈α
and␈α
by␈α
giving␈α
the
␈↓ ↓Hvalue␈αfor␈αlarger␈αintegers␈α
in␈α
terms␈α
of␈α
smaller␈α
ones.␈α
No␈α
single␈α
definition␈α
is␈α
generally␈α
accepted,␈α
so␈α
we␈α
shall␈α
give
␈↓ ↓Hexamples␈α
of␈α
increasing␈α
complexity.

␈↓ ↓H
␈↓ α_1. The Fibonacci sequence is given by the equations
␈↓ ↓H

␈↓ ↓H
        ␈↓↓f␈↓α0␈↓↓ = 1
␈↓ ↓H

␈↓ ↓H
        f␈↓α1␈↓↓ = 1
␈↓ ↓H

␈↓ ↓H
        f␈↓αn+1␈↓↓ = f␈↓αn␈↓↓ + f␈↓αn-1.␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ α_2.␈α
When␈α
differential␈α
equations␈α
are␈α
to␈α
be␈α
solved␈α
numerically,␈α
recursion␈α
relations␈α
such␈α
as

␈↓ ↓H
     ␈↓↓f(x␈↓α0␈↓↓ + nh) = F(f(x␈↓α0␈↓↓ + (n-1)h) , f(x␈↓α0␈↓↓ + (n-2)h) , . . . , f(x␈↓α0␈↓↓ + (n-k)h))␈↓
␈↓ ↓H

␈↓ ↓H

␈↓ ↓H
arise where ␈↓↓f␈↓  is in general a vector of real numbers.
␈↓ ↓H

␈↓ ↓H
␈↓ α_3.␈α
When␈α
linear␈α
differential␈α
equations␈α
are␈α
solved␈α
by␈α
series,␈α
recursion␈αrelations␈αfor␈αthe␈αcoefficients␈αof
␈↓ ↓Hthe␈α
powers␈α
of␈α
the␈α
independent␈α
variables␈α
arise.

␈↓ ↓H
Recursive functions
␈↓ ↓H

␈↓ ↓H
␈↓ α_The␈α⊃systematic␈α⊃study␈α⊃of␈α⊃recursion␈α⊃began␈α⊃in␈α⊃the␈α⊃1920's␈α⊃when␈α⊃mathematical␈α⊃logic␈α⊂began␈α⊂to␈α⊂treat
␈↓ ↓Hquestions␈αof␈αdefinability,␈αcomputability␈αand␈αdecidability.␈αAn␈αimportant␈αrole␈αis␈αplayed␈αby␈αprimitive␈αrecursive
␈↓ ↓Hfunctions.

␈↓ α_Primitive␈α↔recursive␈α↔functions␈α↔are␈α↔integer␈α↔functions␈α⊗of␈α⊗integers␈α⊗built␈α⊗up␈α⊗from␈α⊗addition␈α⊗and
␈↓ ↓Hmultiplication␈α∞of␈α∞integers␈α∞and␈α∞previously␈α∞defined␈α∞primitive␈α∞recursive␈α∞functions␈α∞by␈α∞the␈α
primitive␈α
recursion
␈↓ ↓Hscheme

␈↓ ↓H
        ␈↓↓f(0 , x␈↓α2␈↓↓ , . . . , x␈↓αn␈↓↓) = g(x␈↓α2␈↓↓ , . . . , x␈↓αn␈↓↓)
␈↓ ↓H

␈↓ ↓H
␈↓ α_f(x␈↓α1␈↓↓ + 1, x␈↓α2␈↓↓ , . . . , x␈↓αn␈↓↓) = h(f(x␈↓α1␈↓↓ , . . . , x␈↓αn␈↓↓),x␈↓α2␈↓↓, . . . , x␈↓αn␈↓↓n) .␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ α_Here␈α␈↓↓g␈↓␈αand␈α
␈↓↓h␈↓␈α
are␈α
primitive␈α
recursive␈α
functions␈α
of␈α
␈↓↓n-1␈↓␈α
and␈α
␈↓↓n+1␈↓␈α
arguments␈α
respectively.␈α
As␈α
an␈α
example,
␈↓ ↓Hwe␈α
define␈α
␈↓↓n!␈↓␈α
by

␈↓ α_0!␈α
=␈α
1

␈↓ ↓Hand

␈↓ α_␈↓↓(n+1)!␈α
=␈α
(n+1).n!␈↓

␈↓ ↓Hso␈α
that␈α
in␈α
this␈α
case␈α
␈↓↓g␈↓␈α
is␈α
a␈α
function␈α
of␈α
0␈α
arguments,␈α
namely␈α
the␈α
constant␈α
1,␈α
and␈α
␈↓↓h(u,v)␈α
=␈α
(v+1)u.␈↓

␈↓ ↓H
␈↓ α_All␈α∩the␈α∩common␈α⊃functions␈α⊃of␈α⊃number␈α⊃theory␈α⊃are␈α⊃primitive␈α⊃recursive.␈α⊃Moreover,␈α⊃many␈α⊃important
␈↓ ↓Hfunctions␈αon␈αother␈αcountable␈αdomains␈αthan␈αthe␈αintegers␈α
correspond␈α
to␈α
primitive␈α
recursive␈α
functions␈α
when␈α
we
␈↓ ↓Hchoose␈α
a␈α
specific␈α
enumeration␈α
for␈α
the␈α
domain.

␈↓ ↓H
␈↓ α_Primitive␈α∞recursive␈α∞functions␈α∞are␈α∞included␈α∞in␈α∞general␈α∞recursive␈α
functions.␈α
The␈α
definition␈α
of␈α
general
␈↓ ↓Hrecursive␈α
function␈α
is␈α
like␈α
that␈α
given␈α
above␈α
for␈α
primitive␈α
recursive␈α
functions␈α
except␈α
that␈α
the␈α
relations␈α
are
␈↓ ↓Hreplaced␈αby␈αan␈αarbitrary␈αfinite␈αcollection␈αof␈αequations␈αrelating␈αthe␈αvalues␈αof␈α␈↓↓f␈↓␈αfor␈αdifferent␈αarguments,␈αand
␈↓ ↓Hthe␈αfunction␈αis␈αconsidered␈αdefined␈α␈↓βif␈αand␈αonly␈αif␈↓␈αa␈αunique␈αvalue␈αof␈α␈↓↓f(x␈↓α1␈↓↓␈α,␈α.␈α.␈α.␈α,␈αx␈↓αn␈↓↓)␈↓␈αcan␈αbe␈αdeduced␈αfrom␈αthe
␈↓ ↓Hequations␈αfor␈αeach␈α␈↓↓n␈↓-tuplet␈α␈↓↓(x␈↓α1␈↓↓␈α,␈α.␈α.␈α.␈α,␈αx␈↓αn␈↓↓)␈↓.␈αNaturally,␈αif␈αsomeone␈αgives␈αyou␈αan␈αarbitrary␈αcollection␈αof␈αsuch
␈↓ ↓Hrelations,␈αyou␈αmay␈αnot␈αbe␈αable␈αto␈αdetermine␈αwhether␈α␈↓↓f(x␈↓α1␈↓↓␈α,␈α.␈α.␈α.␈α,␈αx␈↓αn␈↓↓)␈↓␈αis␈αuniquely␈α
determined,␈α
so␈α
you␈α
may␈α
not
␈↓ ↓Hknow␈αwhether␈αyou␈αhave␈αa␈αgeneral␈αrecursive␈αfunction␈αor␈αnot.␈αThis␈αdifficulty␈αis␈αunavoidable.␈αThere␈αis␈αno␈αway
␈↓ ↓Hto␈αgive␈αa␈αdefinition␈αscheme␈αthat␈αis␈αalways␈αguaranteed␈αto␈αgive␈αa␈αfunction␈αbut␈αwhich␈αwill␈αgive␈αall␈α
computable
␈↓ ↓Hfunctions.␈α∞This␈α∞fact␈α∞is␈α∞itself␈α∞expressed␈α∞in␈α∞the␈α∞terminology␈α∞of␈α∞recursive␈α∞function␈α∞theory␈α∞by␈α∞the␈α
statement
␈↓ ↓Hthat␈αthe␈αset␈αof␈αcomputable␈αfunctions␈αis␈αrecursively␈αenumerable␈αbut␈αnot␈αrecursive.␈αThe␈αfamous␈αexample␈αof␈αa
␈↓ ↓Hgeneral␈α∩recursive␈α∩function␈α∩that␈α∩is␈α∩not␈α∩primitive␈α∩recursive␈α∩is␈α∩the␈α∩Ackermann␈α∩function␈α∩defined␈α∩by␈α∩the
␈↓ ↓Hequations

␈↓ ↓H
␈↓ α_␈↓↓A(0,n,p) = n + p,
␈↓ ↓H
␈↓ α_A(1,0,p) = 0,
␈↓ ↓H
␈↓ α_A(2,0,p) = 1,
␈↓ ↓H
␈↓ α_A(m+1,0,p) = p ␈↓if ␈↓↓p␈↓ > 1, and
␈↓ ↓H
␈↓ α_A(m+1,n+1,p) = A(m,A(m+1,n,p),p).␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ α_An␈α∞important␈α∞result␈α∞for␈α∞computer␈α
science␈α
is␈α
that␈α
the␈α
general␈α
recursive␈α
functions␈α
coincide␈α
with␈α
the
␈↓ ↓Hfunctions␈α∞defined␈α∞by␈α∞Turing␈α∞machines␈α∞which␈α∞are␈α∞a␈α∞simple␈α
form␈α
of␈α
computer.␈α
They␈α
also␈α
coincide␈α
with␈α
the
␈↓ ↓Hfunctions␈α⊂of␈α⊂integers␈α⊂defined␈α⊂by␈α⊂Algol␈α⊂or␈α⊂Fortran␈α⊂programs␈α⊂assuming␈α⊂that␈α⊂the␈α⊂program␈α∂can␈α∂cope␈α∂with
␈↓ ↓Hwhatever␈α
size␈α
integers␈α
arise.

␈↓ ↓H
␈↓ α_Both␈α∀programs␈α∀and␈α∀general␈α∀recursion␈α∀schemata␈α∀in␈α∀general␈α∀give␈α∪partial␈α∪functions,␈α∪because␈α∪the
␈↓ ↓Hcomputation␈α
may␈α
terminate␈α
for␈α
some␈α
values␈α
of␈α
the␈α
arguments␈α
and␈α
not␈α
for␈α
others.

␈↓ ↓H
␈↓ α_The␈α
study␈α
of␈α
computable␈α
functions␈α
is␈α
the␈α
domain␈α
of␈α
recursive␈α
function␈α
theory,␈α
an␈αactive␈αbranch␈αof
␈↓ ↓Hmathematics.␈αThe␈αconnection␈αbetween␈αcurrent␈αresearch␈αin␈αrecursive␈αfunction␈αtheory␈αand␈αcomputing␈αpractice
␈↓ ↓Hor␈α∂even␈α∂current␈α∂research␈α∂in␈α∞computer␈α∞science␈α∞is␈α∞rather␈α∞tenuous.␈α∞This␈α∞situation␈α∞might␈α∞change␈α∞because␈α∞of
␈↓ ↓Hdevelopments␈α
in␈α
either␈α
field.

␈↓ ↓H

␈↓ ↓H
Recursive procedures
␈↓ ↓H

␈↓ ↓H
␈↓ α_In␈αprogramming,␈αit␈αis␈αfrequently␈αconvenient␈αto␈αhave␈αa␈αprocedure␈αuse␈αitself␈αas␈αa␈αsubprocedure.␈αIf␈αthe
␈↓ ↓Hprocedure␈α∂does␈α∂this,␈α∂it␈α∂is␈α∂called␈α∂recursive.␈α∂Recursive␈α∂procedures␈α∞are␈α∞particularly␈α∞natural␈α∞in␈α∞dealing␈α∞with
␈↓ ↓Hsymbolic␈αexpressions,␈αbecause␈αthe␈αstructure␈αof␈αthe␈αprograms␈αoften␈αmatch␈αthe␈αstructure␈αof␈αthe␈αdata.␈αAs␈αfar
␈↓ ↓Has␈α⊃programming␈α⊃languages␈α⊃are␈α⊃concerned,␈α⊃recursive␈α⊃procedures␈α⊃are␈α⊃quite␈α⊃natural;␈α⊂it␈α⊂requires␈α⊂a␈α⊂special
␈↓ ↓Hstatement␈α∞in␈α∞the␈α∞definition␈α∞of␈α∞the␈α∞language␈α∞to␈α∞forbid␈α∞them.␈α∞However,␈α∞implementing␈α
them␈α
requires␈α
that␈α
a
␈↓ ↓Hspecial␈α
kind␈α
of␈α
object␈α
code␈α
be␈α
compiled,␈α
and␈α
early␈α
programming␈α
languages␈α
like␈α
Fortran␈α
don't␈α
allow␈α
them.␈α
The
␈↓ ↓Hproblem␈α
is␈α
that␈α
variables␈αin␈αthe␈αprogram␈αcorrespond␈αto␈αlocations␈αin␈αthe␈αmachine,␈αand␈αwhen␈αthe␈αprogram␈αis
␈↓ ↓Hcalled␈α∂by␈α∂itself,␈α∂it␈α∂will␈α∂use␈α∂these␈α∂same␈α∂locations␈α∂forgetting␈α∂their␈α∂previous␈α∂contents.␈α∞Therefore,␈α∞recursive
␈↓ ↓Hprograms␈αuse␈αan␈αarray,␈αcalled␈αthe␈α␈↓↓stack␈↓␈αto␈αstore␈αthe␈αcontents␈αof␈αregisters␈αthat␈αmust␈αbe␈αsaved.␈αThis␈αstorage
␈↓ ↓Hcan␈α∂be␈α∂done␈α∂by␈α∂the␈α∞calling␈α∞routine␈α∞before␈α∞it␈α∞enters␈α∞the␈α∞subroutine␈α∞or␈α∞it␈α∞can␈α∞be␈α∞done␈α∞by␈α∞the␈α∞subroutine
␈↓ ↓Hbefore␈α
it␈α
uses␈α
the␈α
registers,␈α
the␈α
latter␈α
being␈α
more␈α
common.␈α
After␈α
the␈α
registers␈α
have␈α
been␈α
saved␈α
on␈α
the␈α
stack,
␈↓ ↓Hthe␈α
index␈α
into␈α
the␈α
stack␈α
is␈α
increased␈α
by␈α
the␈α
number␈α
of␈α
registers␈α
stored␈α
so␈α
that␈α
subsequent␈α
saving␈α
on␈αthe
␈↓ ↓Hstack␈α
will␈α
use␈α
fresh␈α
registers.␈α
When␈α
the␈α
subroutine␈α
exits␈α
the␈α
contents␈α
of␈α
the␈α
saved␈α
registers␈α
are␈αrestored
␈↓ ↓Hfrom␈α
the␈α
stack␈α
to␈α
their␈α
previous␈α
values␈αand␈αthe␈αstack␈αpointer␈αis␈αreduced␈αby␈αthe␈αamount␈αit␈αwas␈αpreviously
␈↓ ↓Hincreased.␈αThis␈αis␈αdone␈αby␈αthe␈αcaller␈αor␈αby␈αthe␈αsubroutine␈αaccording␈αto␈αwhether␈αthe␈α
caller␈α
or␈α
subroutine␈α
did
␈↓ ↓Hthe␈αoriginal␈αstoring.␈αAn␈αalternative␈αtechnique␈αis␈αto␈αuse␈αthe␈αstack␈αfor␈αall␈αtemporary␈αregisters.␈α
In␈α
this␈α
case,␈α
it
␈↓ ↓His␈α
unnecessary␈α
to␈αmove␈αdata␈αaround␈αand␈αit␈αis␈αonly␈αnecessary␈αto␈αchange␈αthe␈αstack␈αpointer␈αwhen␈αsubroutines
␈↓ ↓Hare␈αentered␈αand␈αleft.␈αHowever,␈αthis␈αtechnique␈αuses␈αup␈αthe␈αindexing␈αcapabilities␈αof␈αsome␈αmachines␈αwhich␈αmay
␈↓ ↓Hbe␈α∪wanted␈α∪for␈α∪other␈α∪purposes.␈α∩Recursive␈α∩programs␈α∩can␈α∩be␈α∩written␈α∩in␈α∩any␈α∩programming␈α∩language␈α∩by
␈↓ ↓Hexplicitly␈α
programming␈α
the␈α
saving␈α
and␈α
restoring.

␈↓ α_The␈αfirst␈αlanguage␈αto␈αuse␈α
recursive␈α
subroutines␈α
on␈α
a␈α
regular␈α
basis␈α
were␈α
the␈α
IPL␈α
languages␈α
of␈α
Newell,
␈↓ ↓HShaw␈α∂and␈α∂Simon.␈α∂Lists␈α∂were␈α∞used␈α∞for␈α∞the␈α∞stack␈α∞and␈α∞the␈α∞saving␈α∞and␈α∞restoring␈α∞was␈α∞done␈α∞explicitly␈α∞by␈α∞the
␈↓ ↓Hprogrammer.␈α
The␈α
first␈αlanguage␈αprovide␈αan␈αautomatic␈αmechanism␈αfor␈αrecursion␈αwas␈αLISP.␈αAlgol␈α60␈αand␈αits
␈↓ ↓Hsuccessors␈α
allow␈α
recursion.

␈↓ α_Many␈αcomputers␈αhave␈αspecial␈αinstruction␈αfor␈αhandling␈αstacks,␈αe.g.␈αthe␈αPUSH␈αand␈αPOP␈αinstructions␈αof
␈↓ ↓Hthe␈α⊃Digital␈α⊃Equipment␈α⊃PDP-10.␈α⊃Other␈α⊃machines,␈α⊃such␈α⊃as␈α⊃the␈α⊂Burroughs␈α⊂5000␈α⊂and␈α⊂its␈α⊂successors,␈α⊂have
␈↓ ↓Hinstructions␈α⊃that␈α⊃use␈α⊃a␈α⊃hardware␈α⊃stack␈α⊃directly.␈α⊃These␈α⊃special␈α⊃facilities␈α⊃give␈α⊃a␈α⊂modest␈α⊂increase␈α⊂in␈α⊂the
␈↓ ↓Hefficiency␈α
of␈α
recursive␈α
programming.

␈↓ ↓H

␈↓ ↓H
Recursive conditional expressions
␈↓ ↓H

␈↓ ↓H
␈↓ α_The␈αrecursive␈αuse␈αof␈αconditional␈αexpressions␈αprovides␈αan␈αeconomical␈α
and␈α
elegant␈α
way␈α
of␈α
specifying␈α
the
␈↓ ↓Hfunctions␈αthat␈αare␈αcomputable␈αin␈αterms␈αof␈αa␈αcollection␈αof␈αbase␈αfunctions.␈αThis␈αtechnique␈αis␈αthe␈αbasis␈αof␈αthe
␈↓ ↓HLISP␈α
programming␈α
language␈α
and␈α
also␈α
of␈α
the␈α
theoretical␈α
system␈α
of␈αD.␈αScott␈αfor␈αstudying␈αthe␈αproperties␈αof
␈↓ ↓Hcomputer␈α
programs.

␈↓ ↓H
␈↓ α_A conditional expression has the form, in Algol notation, of
␈↓ ↓H

␈↓ ↓H

␈↓ ↓H
        ␈↓βif ␈↓↓p ␈↓βthen ␈↓↓a ␈↓βelse ␈↓↓b␈↓.
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HIt␈αis␈αevaluated␈αby␈αfirst␈αevaluating␈αthe␈αpropositional␈αexpression␈α␈↓↓p␈↓.␈αIf␈α␈↓↓p␈↓␈αis␈α␈↓βtrue␈↓,␈αthe␈αvalue␈αof␈αthe␈αconditional
␈↓ ↓Hexpression␈αis␈αthat␈αof␈α␈↓↓a␈↓,␈αand␈αif␈αthe␈αvalue␈αof␈α␈↓↓p␈↓␈αis␈α␈↓βfalse␈↓,␈αthe␈αvalue␈αof␈αthe␈α
conditional␈α
expression␈α
is␈α
that␈α
of␈α
␈↓↓b␈↓.␈α
It
␈↓ ↓His␈α
important␈α
to␈α
note␈α
that␈α
only␈α
one␈α
of␈α
␈↓↓a␈↓␈α
or␈α
␈↓↓b␈↓␈α
is␈α
actually␈α
evaluated.

␈↓ α_A␈α
simple␈α
example␈α
of␈α
the␈α
use␈α
of␈α
conditional␈α
expressions␈α
is␈α
to␈α
define␈α
the␈α
absolute␈α
value␈α
of␈α
a␈α
number␈α
by

␈↓ ↓H
␈↓ α_␈↓↓|x| = ␈↓βif␈↓↓ x < 0 ␈↓βthen␈↓↓ -x ␈↓βelse␈↓↓ x.␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ α_Conditional␈α
expressions␈α
are␈α
used␈α
to␈α
define␈α
functions␈α
recursively␈α
by␈α
writing␈α
the␈α
definition␈α
in␈α
the␈α
form

␈↓ ↓H
       ␈↓ α_␈↓↓f(x , . . . , z) ← ␈↓∧E␈↓↓{x , . . . , z, f , g , . . . , h}␈↓,
␈↓ ↓H

␈↓ ↓H
␈↓ ↓Hwhere␈α
␈↓∧E␈↓␈α
is␈α
an␈α
expression␈α
involving␈α
the␈α
variables,␈↓↓x␈α
,␈α
.␈α
.␈α
.␈α
,␈α
z␈↓,␈α
the␈α
function␈α␈↓↓f␈↓␈αbeing␈αdefined,␈αand␈αknown␈αor
␈↓ ↓Hpreviously␈α
defined␈α
functions␈α
␈↓↓g␈α
,␈α
.␈α
.␈α
.␈α
,␈α
h␈↓.

␈↓ α_An␈α
example␈α
of␈α
such␈α
a␈α
definition␈α
is

␈↓ ↓H
(␈↓↓a␈↓)␈↓ α_␈↓↓n! ← ␈↓βif␈↓↓ n = 0 ␈↓βthen␈↓↓ 1 ␈↓βelse␈↓↓ n.(n-1)!␈↓.
␈↓ ↓H

␈↓ ↓H
␈↓ α_The␈αgeneral␈αmethod␈αfor␈αevaluating␈αrecursive␈αconditional␈αexpressions␈αis␈αillustrated␈αby␈αusing␈αthe␈α
above
␈↓ ↓Hdefinition␈α
to␈α
evaluate␈α
3!.␈α
Namely,␈α
we␈α
have

␈↓ ↓H
        3! = ␈↓βif␈↓↓ 3=0 ␈↓βthen ␈↓↓1 ␈↓βelse ␈↓↓3.(3-1)!
␈↓ ↓H
       ␈↓ α_   = 3.2! =3.(␈↓βif␈↓↓ 2=0 ␈↓βthen ␈↓↓1 ␈↓βelse ␈↓↓2.(2-1)!)
␈↓ ↓H
␈↓ α_   = 3.2.(␈↓βif ␈↓↓1=0 ␈↓βthen ␈↓↓1 ␈↓βelse ␈↓↓1.(1-1)!)
␈↓ ↓H
␈↓ α_   = 3.2.1.(␈↓βif ␈↓↓0=0 ␈↓βthen ␈↓↓1 ␈↓βelse ␈↓↓0.(0-1)!)
␈↓ ↓H
␈↓ α_   = 3.2.1.1 = 6.␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HNote␈α⊂that␈α⊂the␈α⊂rule␈α⊂for␈α⊂evaluating␈α⊂conditional␈α⊂expressions␈α⊂ensures␈α∂that␈α∂the␈α∂computer␈α∂never␈α∂attempts␈α∂to
␈↓ ↓Hevaluate␈α
(-1)!.␈α
This␈α
is␈α
necessary␈α
since␈α
its␈α
evaluation␈α
wouldn't␈α
terminate.

␈↓ α_As␈α
a␈α
second␈α
example,␈α
the␈α
Ackermann␈α
function␈α
mentioned␈α
above␈αis␈αwritten␈αas␈αa␈αrecursive␈αconditional
␈↓ ↓Hexpression␈α
as␈α
follows:

␈↓ ↓H
␈↓ α_␈↓↓A(m,n,p) ←
␈↓ ↓H
␈↓ α_␈↓ αh␈↓βif ␈↓↓m = 0 ␈↓βthen ␈↓↓n + p
␈↓ ↓H
␈↓ α_␈↓ αh␈↓βelse if ␈↓↓n = 0 ␈↓βthen ␈↓↓(␈↓βif ␈↓↓m = 1 ␈↓βthen ␈↓↓0␈↓β else if ␈↓↓m = 2 ␈↓βthen ␈↓↓1␈↓β else ␈↓↓p)
␈↓ ↓H
␈↓ α_␈↓ αh␈↓βelse ␈↓↓A(m - 1,A(m,n - 1,p),p).␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ α_Several␈α
remarks␈α
are␈α
worth␈α
making:

␈↓ α_First,␈α∪in␈α∪a␈α∪programming␈α∩language␈α∩that␈α∩uses␈α∩recursive␈α∩conditional␈α∩expressions,␈α∩3!␈α∩would␈α∩not␈α∩be
␈↓ ↓Hevaluated␈αby␈αthe␈αabove␈αsymbolic␈αmanipulation.␈αEither␈α␈↓↓(a)␈↓␈αwould␈αbe␈αcompiled␈α
into␈α
a␈α
recursive␈α
subroutine␈α
(i.e.
␈↓ ↓Ha␈αsubroutine␈αof␈αthe␈αtype␈αexplained␈αabove␈αthat␈αcalls␈αitself␈αand␈αuses␈αa␈αstack␈αto␈αsave␈αintermediate␈αresults␈αand
␈↓ ↓Hreturn␈α
addresses)␈α
or␈α
a␈α
recursive␈α
interpreter␈α
would␈α
interpret␈α
a␈α
list␈α
structure␈α
version␈α
of␈α
␈↓↓(a)␈↓.

␈↓ α_Second,␈α␈↓↓(a)␈↓␈αcan␈αeasily␈αbe␈αreplaced␈αby␈αanother␈αexpression␈αfor␈αthe␈αfactorial␈αthat␈αcan␈αbe␈αcompiled␈αinto␈αa
␈↓ ↓Hnon-recursive␈α
program.␈α
Namely,␈α
we␈α
write

␈↓ ↓H
(␈↓↓b␈↓)␈↓ α_␈↓↓n! ← fact(n, 0, 1)␈↓
␈↓ ↓H

␈↓ ↓H
where
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓fact(n, m, p) ← ␈↓βif␈↓↓ m = n ␈↓βthen ␈↓↓p ␈↓βelse ␈↓↓fact(n, m+1,(m+1)p).
␈↓ ↓H

␈↓ ↓H
␈↓ ↓H(b)␈α
␈↓can␈αbe␈αtranslated␈αinto␈αa␈αnon-recursive␈αprogram,␈αbecause␈αthe␈αonly␈αoccurrence␈αof␈α␈↓↓fact␈↓␈αon␈αthe␈αright␈αhand
␈↓ ↓Hside␈αof␈αthe␈αdefinition␈αappears␈αat␈αthe␈αouter␈αlevel,␈αi.e.␈α␈↓↓fact(n,␈αm+1,(m+1)p)␈↓␈αgives␈αthe␈αvalue␈αof␈α␈↓↓fact(n,␈αm,␈αp)␈α␈↓in
␈↓ ↓Hcontrast␈αto␈αthe␈αthe␈αsituation␈αin␈α␈↓↓(a)␈α␈↓where␈α␈↓↓(n-1)!␈α␈↓must␈αbe␈αmultiplied␈αby␈α␈↓↓n␈α␈↓to␈αgive␈α␈↓↓n!.␈α␈↓This␈αallows␈αthe␈αobject
␈↓ ↓Hprogram␈α∂to␈α∂contain␈α∂an␈α∂ordinary␈α∂jump␈α∂to␈α∂itself␈α∂rather␈α∂than␈α∂a␈α∞subroutine␈α∞call.␈α∞When␈α∞this␈α∞is␈α∞possible,␈α∞the
␈↓ ↓Hfunction␈α⊃definition␈α⊃is␈α⊃called␈α⊃iterative.␈α⊃Thus␈α⊃␈↓↓fact␈↓␈α⊃is␈α⊃iterative␈α⊃while␈α⊃the␈α⊂definition␈α⊂␈↓↓(a)␈α⊂␈↓is␈α⊂not.␈α⊂Recursive
␈↓ ↓Hdefinitions␈αcannot␈αin␈αgeneral␈αbe␈αreplaced␈αby␈αiterative␈αdefinitions␈αexcept␈αby␈αencoding␈αthe␈αstack␈αas␈αa␈αvariable
␈↓ ↓Hin␈α
the␈α
program,␈α
and␈α
if␈α
this␈α
has␈α
to␈α
be␈α
done,␈α
there␈α
is␈α
no␈α
advantage␈α
in␈α
the␈α
replacement.

␈↓ α_Third,␈αthere␈αmay␈αbe␈αseveral␈αoccurrences␈αof␈αthe␈αfunction␈αbeing␈αdefined␈αon␈αthe␈αright␈αhand␈αside␈αof␈αthe
␈↓ ↓Hrecursive␈α∞definition,␈α∞and␈α∞whether␈α∞the␈α∞evaluation␈α∞terminates␈α∞may␈α∞depend␈α
on␈α
which␈α
occurrence␈α
is␈α
evaluated
␈↓ ↓Hfirst.␈α
The␈α
following␈α
example␈α
due␈α
to␈α
Morris␈α
shows␈α
this:

␈↓ ↓H
␈↓ α_␈↓↓f(x,y) ← ␈↓βif ␈↓↓x=0 ␈↓βthen ␈↓↓0 ␈↓βelse ␈↓↓f(x-1 , f(y-2, x)).␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HThe␈α
reader␈α
should␈α
evaluate␈α
␈↓↓f(2,1)␈↓␈α
to␈α
convince␈α
himself.

␈↓ α_It␈αis␈αalso␈αpossible␈αto␈αuse␈αrecursive␈αconditional␈αexpressions␈αto␈αdefine␈αfunctions␈αthat␈αtake␈αfunctions␈αas
␈↓ ↓Harguments␈α⊃or␈α⊃give␈α⊃functions␈α⊂as␈α⊂results.␈α⊂However,␈α⊂there␈α⊂remain␈α⊂unsolved␈α⊂problems␈α⊂in␈α⊂getting␈α⊂compiling
␈↓ ↓Halgorithms␈α
that␈α
give␈α
efficient␈α
object␈α
code␈α
and␈α
give␈α
the␈α
"right"␈α
answers␈α
in␈α
all␈α
cases.

␈↓ α_The␈αterm␈α␈↓↓recursive␈↓␈αis␈αalso␈αsometimes␈αapplied␈αto␈αthe␈αthe␈αBackus-Naur␈αform␈αused␈αto␈αdefine␈αclasses␈αof
␈↓ ↓Hstrings␈α
of␈α
symbols.